//
// Description: 6017. 向数组中追加 K 个整数
// Created by Loading on 2022/3/6.
//

#include <bits/stdc++.h>

using namespace std;

long long minimalKSum(vector<int> &nums, int k) {
    long long res = 0;
    sort(nums.begin(), nums.end());

    int last = 0;
    for (auto x : nums) {
        // 与last元素之间存在其他元素时，进入填充
        if (x > last + 1) {
            // 需填充数量不足间隙，跳出
            if (k <= x - last - 1) {
                break;
            }
            k -= x - last - 1;
            // 累计和
            res += (last * 1ll + x) * (x - last - 1) / 2;
        }
        last = x;
    }

    // 数组遍历完成仍需填充时，从last继续向后累加
    return res + (last * 1ll + 1 + last + k) * k / 2;
}

int main() {
    vector<int> nums{{96, 44, 99, 25, 61, 84, 88, 18, 19, 33, 60, 86, 52, 19, 32, 47, 35, 50, 94, 17, 29, 98, 22, 21, 72, 100, 40, 84}};
    int k = 35;
    auto res = minimalKSum(nums, k);
    cout << res << endl;

    return 0;
}